#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool isValid(string s) {
    stack<char> mystack;
    for(int i=0;i<s.length();i++){
        if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
            mystack.push(s[i]);
        }else if(s[i] == ')'){
            if(mystack.empty() || mystack.top() != '(') return 0;
            mystack.pop();
        }else if(s[i] == ']'){
            if(mystack.empty() || mystack.top() != '[') return 0;
            mystack.pop();
        }else if(s[i] == '}'){
            if(mystack.empty() || mystack.top() != '{') return 0;
            mystack.pop();
        }
    }
    if(mystack.empty()) return 1;
    return 0;
}

int main(){
    return 0;
}